home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 7128 < prev    next >
Encoding:
Text File  |  1996-08-05  |  5.4 KB  |  132 lines
  1. Newsgroups: comp.sys.amiga.programmer
  2. Path: news.ifm.liu.se!liuida!news
  3. From: c92manen@und.ida.liu.se (Mans Engman)
  4. Subject: Re: 680X0 -> PPC translator?
  5. X-Nntp-Posting-Host: astmatix.ida.liu.se
  6. Message-ID: <4770.6673T831T125@und.ida.liu.se>
  7. Sender: news@ida.liu.se
  8. Organization: CIS Dept, Linkoping University, Sweden
  9. X-Newsreader: THOR 2.22 (Amiga;TCP/IP) *UNREGISTERED*
  10. References: <31499F8E.26A9@netvision.net.il> <volker.0fw1@vb.franken.de><315800D7.1854@sapiens.com>
  11.     <volker.0g32@vb.franken.de><315C198B.49C2@netvision.net.il>
  12.     <volker.0g5w@vb.franken.de><1996Apr2.230841.8275@scala.scala.com>
  13.     <31640B0C.23F5@netvision.net.il> <1586.6669T961T2657@und.ida.liu.se> <31695324.57C8@netvision.net.il>
  14. Date: Tue, 9 Apr 1996 12:51:02 GMT
  15.  
  16.  
  17. >Mans Engman wrote:
  18. >>
  19. >> Once you think a bit, it's easy to show (prove!) that static code<->data
  20. >> distinction can't be determined by an algorithm. It is what theorists call
  21. >> an "undecidable" problem. Granted, for a "real" computer with a finite
  22. >> amount of memory/indata it can be "solved" by brute-force search, but this
  23. >> is not a practical approach.
  24.  
  25. >many problems aren't solvable with today's technology, but it doesn't mean
  26. >they're not solvable with other yet-to-devised methods, now do they??
  27.  
  28. What do you mean? You think someone will come up with algorithms to solve
  29. problems *beyond* what a Turing machine can?
  30.  
  31. >>
  32. >> Okay, let's go on:
  33. >>
  34. >> 1) Hilberts 10th problem is a well known, proven undecidable problem. The
  35. >> problem is determining whether an integer polynomial equation has a
  36. >> (integer) solution.
  37.  
  38. >oh please, stick to the subject at hand and stop making irrelevant analogies.
  39.  
  40. This isn't an "irrelevant analogy", it's a simple example (among *many*
  41. undecidable problems) used to construct a program for which you can't analyse
  42. the program flow statically.
  43.  
  44. >> 2) Now imagine a program calculating some function on the indata x, y, ...
  45. >> and uses the result as a pc-relative address where we jump. This function,
  46. >> and the rest of the program can be constructed such that for all x, y, ...
  47. >> we jump to a legal piece of code. Between these code chunks we will of
  48. >> course put data to confuse anyone analysing the program! :)
  49.  
  50. >you havn't really thought about the implementation of your hypothetic
  51. >scenario have you?! in order for what you said to work you must store the
  52. >offsets from the current locations in some array, and the inputs are used to
  53. >calculate the array entry that should be selected that's all.
  54.  
  55. No, I didn't intend using an array.
  56. I can easily construct a function that will be within certain bounds,
  57. and will always be a multiple of, say, 42, and you'll not be able to
  58. know/prove that by using an algorithm. That's the whole point of the example;
  59. the function itself is very easy to calculate, but it is undecidable what the
  60. possible results will be.
  61.  
  62. Even if you use an array, you'd have exactly the same problem trying to know
  63. which elements of the array are used as code pointers, and which of them are
  64. something completely different. Like pointers to data which looks like
  65. code, but isn't used as such (see below).
  66.  
  67. >calculating the
  68. >correct number of bytes to skip from arbitrary inputs without using this
  69. >method is next to impossible and most practical applications don't use this
  70. >method.
  71.  
  72. It's perhaps not practical to have this very-advanced-function(tm) to
  73. calculate jump-addresses, but it's legal and possible.
  74.  
  75. >you can't confuse the analysing program because ALL code sequences
  76. >can be identified without a problem, every sequence of words that makes sense
  77. >as a code sequence must be executable code and therefore can be identified.
  78. >by 'makes sense' i mean that the code makes references to other parts of the
  79. >program and a sequence of code instructions is  maintained, you simply have
  80. >to follow the logic of that section and see if it's interrupted by some data
  81. >word without a jump that would prevent such a thing from happening.
  82.  
  83. What you or your analyser thinks "makes sense" as executable code is not
  84. neccessarily code that will be executed.
  85.  
  86. For instance, if some
  87. section of my program is
  88.  
  89. $7070
  90. $c1c1
  91. $4e75
  92.  
  93. and I some of the words as data (nice bit masks), you have
  94. no right to interpret the sequence as
  95.  
  96. moveq   #112,d0
  97. muls    d1,d0
  98. rts
  99.  
  100. even though that would "make sense" as legal code.
  101.  
  102. The best thing you can do about this is to have the both the original data
  103. and the translated part, in the final translated program.
  104. Then, you could determine, at *run-time*, how it is used.
  105.  
  106. Or how about a compiler with "code chunks" that are actually used as data to
  107. generate the output? If your algorithm translates that code (which it should
  108. according to your algorithm), then it would magically be PPC compiler!?
  109. Granted, that would be a great accomplishment, so if you succeed with that,
  110. I'm impressed :)
  111.  
  112. >you might
  113. >wanna defer the translation until you make sure this section is actually
  114. >being called from somewhere alse.
  115.  
  116. Which you can't, for all cases, determine before run-time.
  117.  
  118. >> i)  try different combinations of inputs and simulate the program. Inputs
  119. >> include outside calls, memory reads (that may change anytime), or other
  120. >> undecidable functions. To be sure the algorithm would have to try *all* of
  121. >> them. Combinatorial-explosion-city?
  122.  
  123. >not true, as the code makes a jump using the array i mentioned and therefore
  124. >i know the possible offsets that exist.
  125.  
  126. True, whether you use an array (which you incorrectly assume) or not.
  127.  
  128. >Avi Lev.
  129.  
  130. /Mans (.sig being recompiled)
  131.  
  132.